package leetcode_1301_1400;

import java.util.Arrays;
import java.util.Comparator;

public class LeeCode_1340 {
    public static void main(String[] args) {
//        System.out.println(maxJumps(new int[]{6,4,14,6,8,13,9,7,10,6,12}, 2));
//        System.out.println(maxJumps(new int[]{7,6,5,4,3,2,1}, 1));
//        System.out.println(maxJumps(new int[]{6,1,7,1,6,1}, 2));
    }
    int[] arr;
    int n;
    int[] dp;
    int d;
    public int maxJumps(int[] arr, int d) {
        this.arr = arr;
        this.n = arr.length;
        this.d = d;
        this.dp = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, getMax(i));
        }
        return ans;
    }
    public int getMax(int p){
        if (dp[p] != 0)
            return dp[p];
        int l = 1, lMax = 0;
        while (p - l >= 0 && l <= d){
            if (arr[p - l] >= arr[p]){
                break;
            }else {
                if (dp[p - l] == 0){
                    dp[p - l] = getMax(p - l);
                }
                lMax = Math.max(lMax, dp[p - l]);
                l++;
            }
        }
        int r = 1, rMax = 0;
        while (p + r < n && r <= d){
            if (arr[p + r] >= arr[p]){
                break;
            }else {
                if (dp[p + r] == 0){
                    dp[p + r] = getMax(p + r);
                }
                rMax = Math.max(rMax, dp[p + r]);
                r++;
            }
        }
        dp[p] = Math.max(lMax, rMax) + 1;
        return dp[p];
    }
}
